package com.ai.zuochengyun.phase01.class03;

import java.util.ArrayList;
import java.util.List;

public class Code05_SingleLinkedList {

    public static void main(String[] args) {
        System.out.println("测试开始");
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int len = (int) (Math.random() * 10+2);
            int value = (int) (Math.random() * 100+2);
            Node node = generateRandomLinkedList(len, value);
            Node copy = copyNode(node);

            Node node1 = testReverseSingleLinkedList(node);
            Node node2 = reverseSingleLinkedList(copy);
            if (node1 != null && node2 != null && node1.value != node2.value) {
                System.out.println("出错了");
                printNode(copy);
                break;
            }
        }
        System.out.println();
        System.out.println("测试结束");
    }

    /**
     * 拷贝节点
     * @param head
     */
    private static Node copyNode(Node head) {
        if (head == null) {
            return null;
        }
        // 头节点
        Node ans = new Node(head.value);
        Node next = head.next;
        Node cur = ans;
        // 是否还有下一个节点
        while (next != null) {
            cur.next = new Node(next.value);
            next = next.next;
            cur = cur.next;
        }
        return ans;
    }

    /**
     * 动态生成单链表
     *
     * @param len
     * @param value
     * @return
     */
    public static Node generateRandomLinkedList(int len, int value) {
        int size = (int) (Math.random() * (len + 1)) + 2;
        if (size == 0) {
            return null;
        }
        size--;
        Node head = new Node((int) (Math.random() * (value + 1)));
        Node pre = head;
        while (size > 0) {
            Node cur = new Node((int) (Math.random() * (value + 1)));
            // 前一个节点的next指针指向cur
            pre.next = cur;
            // pre来到cur的位置
            pre = cur;
            size--;
        }
        return head;
    }

    /**
     * 使用系统自带的链表来反转
     *
     * @param head
     * @return
     */
    public static Node testReverseSingleLinkedList(Node head) {
        if (head == null) {
            return null;
        }

        List<Node> list = new ArrayList<>();
        Node cur = head;
        while (cur != null) {
            list.add(cur);
            cur = cur.next;
        }

        // 将链表反转
        list.get(0).next = null;
        for (int i = 1; i < list.size(); i++) {
            list.get(i).next = list.get(i - 1);
        }
        return list.get(list.size() - 1);
    }

    public static class Node {
        int value;
        Node next;
        public Node(int value) {
            this.value = value;
        }
        public Node next(Node next) {
            this.next = next;
            return this;
        }
    }

    public static Node reverseSingleLinkedList(Node head) {
        if (head == null) {
            return null;
        }
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }

    // 输出节点
    private static void printNode(Node node) {
        Node head = node;
        while (head != null) {
            System.out.print(head.value + " ");
            head = head.next;
        }
        System.out.println();
    }
}
